package done.normal_101_200;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 144. Binary Tree Preorder Traversal 二叉树的前序遍历
 * <p>
 * 给定一个二叉树，返回它的 前序 遍历。
 * <p>
 * 示例:
 * 输入: [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [1,2,3]
 * <p>
 * 2019-04-21 9:04 PM
 **/
@SuppressWarnings("all")
public class BinaryTreePreorderTraversal {

    List<Integer> arr = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        // 190421 first
        // 190429 second 递归没有一次做出来 非递归也没有一次做出来
        // 190510 third 递归的一次做出来了, 非递归没思路, 非递归还是没有一次做出来
        // 190606 fourth 非递归看答案才做出来，递归没问题
        // 190621 fifth 非递归没做出来，看答案了。递归太简单
        // 190627 sixth 递归

        if (root == null)
            return arr;
        arr.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return arr;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1,
                new TreeNode(4,
                        new TreeNode(5,
                                new TreeNode(9,
                                        11, 12),
                                10),
                        6), new TreeNode(2,
                3, 8));
        info("[1, 4, 5, 9, 11, 12, 10, 6, 2, 3, 8] \n" +
                "                                                ->{}", preorderTraversal(root));
    }
}



















































/*
// 第一种方案 根左右
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while(root!=null||!stack.empty()){
        // 遍历左子树
        while(root!=null){
            // 根
            result.add(root.val);
            stack.push(root);
            root = root.left;
        }

        // 设置为左子树的右子树
        if(!stack.isEmpty()){
            root = stack.pop();
            root = root.right;
        }
    }
    return result;

}

// 第一种方案 递归
public List<Integer> preorderTraversal(TreeNode root) {
    return new ArrayList(){{
        if (root!=null) {
            add(root.val);
            addAll(preorderTraversal(root.left));
            addAll(preorderTraversal(root.right));
        }
    }};
}
*/
